Some error correction algorithms, such as the Turbo Decoder algorithm, use variations of the MAP algorithm to recover a sequence of information bits from an encoded bit sequence that has been corrupted by noise. The recursive nature of the calculation required by the MAP algorithm makes implementation costly.
For example, FIG. 1 illustrates the sequence output by the MAP algorithm as a function of a set of “forward” metrics, and a set of “backward” metrics. However, each forward metric α(k), is a function of the previous forward metric, α(k−1) and each reverse metric β(k−1), is a function of the next reverse metric, β(k). As illustrated in the timeline diagram of FIG. 1, an architecture that implements this algorithm requires a buffer large enough to hold either all of the forward metrics or all of the reverse metrics such that the other set of metrics can be calculated while the output is calculated, which design leads to a decoder whose latency is proportional to approximately twice the size of the block that needs to be decoded.
In an effort to reduce the buffer required by the MAP algorithm, a modified version of the MAP algorithm, called the sliding window algorithm, has been developed. By making a small approximation in the reverse metric calculations, the sliding window approach reduces the size of the required metric buffer. This is accomplished by dividing the received sequence into windows, and then processing each window.
FIG. 2 illustrates a timeline of how the sliding window calculations are performed when the data has been divided into two windows. The length of the tail and learn size are typically very small compared to the amount of data to be processed. It is clear that as long as the window size is relatively large compared to the size of the learning window, the latency through the decoder is not significantly increased but the size of the buffer required to hold the forward metric is significantly decreased.
Therefore, an objective of the present invention is to reduce both latency and cost associated with implementing such algorithms.